#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    unordered_set<string> st;
    void _permutation(string& str, unordered_set<int>& cnt, string& S)
    {
        if (cnt.size() == S.size())
            st.insert(str);

        for (int i = 0; i < S.size(); i++)
        {
            if (cnt.find(i) == cnt.end())
            {
                cnt.insert(i);
                str += S[i];
                _permutation(str, cnt, S);
                str = str.substr(0, str.size() - 1);
                cnt.erase(i);
            }
        }
    }
    vector<string> permutation(string S) {
        vector<string> ret;
        for (int i = 0; i < S.size(); i++)
        {
            unordered_set<int> cnt;
            cnt.insert(i);
            string str = "";
            str.push_back(S[i]);
            _permutation(str, cnt, S);
        }
        for (auto p : st)
        {
            ret.push_back(p);
        }

        return ret;
    }
};